package com.zlk.algorithm.algorithm.sort.heap;

import com.zlk.algorithm.algorithm.sort.SortUtils;
import org.junit.Test;

import java.util.Arrays;

// 堆结构和堆排序，acm练习风格
// 测试链接 : https://www.nowcoder.com/practice/ed8308a5f0f744fc936bdba78c15f810
// 请同学们务必参考如下代码中关于输入、输出的处理
// 这是输入输出处理效率很高的写法
// 提交以下的code，提交时请把类名改成"Main"，可以直接通过
public class Code01_HeapSort {

    @Test
    public void test1(){

//        int[] arr = new int[]{1,20,4,8,22,4};
//        //输出 1  取整
//        System.out.println(arr[-1/2]);
        int testTimes = 1000;
        int maxVal = 100;
        int maxLen = 30;
        for (int i = 0; i < testTimes; i++) {
            int[] randomArr = SortUtils.getRandomArr(maxVal, maxLen);
            int[] copyArr = Arrays.copyOf(randomArr, randomArr.length);
            Arrays.sort(randomArr);
            sortArray(copyArr);
            if(!SortUtils.isEqual(randomArr,copyArr)){
                System.out.println("fail");
                System.out.println("random:"+randomArr);
                System.out.println("copyArr:"+copyArr);
                return ;
            }
        }
        System.out.println("success!");
    }
    public void sortArray(int[] nums){
        if(nums.length<2||nums==null){
            return ;
        }
        for (int i = 0; i < nums.length; i++) {
            heapInsert(nums,i);
        }
        int size = nums.length;
        SortUtils.swap(nums,0,--size);

        while (size>0){
            heapFiy(nums,0,size);
            SortUtils.swap(nums,0,--size);
        }
    }


    //下沉
    private void heapFiy(int[] nums,int index,int size) {
        int l = (index/2)+1;
        int r = l+1;
        while (l<size){
            int maxIndex = l;
            if(r<size){
                maxIndex=nums[l]>nums[r]?l:r;
            }
            maxIndex = nums[index]>nums[maxIndex]?index:maxIndex;
            if(maxIndex==index){
                return ;
            }else{
                SortUtils.swap(nums,index,maxIndex);
                index = maxIndex;
                l = (index<<1)+1;
                r = l+1;
            }
        }
//        int left  = (index<<1)+1;
//        while (left<size){
//            int right = left+1;
//            int bigIndex = right<size&&nums[left]<nums[right]?right:left;
//            bigIndex = nums[index]>nums[bigIndex]?index:bigIndex;
//            if(bigIndex==index){
//                break;
//            }
//            SortUtils.swap(nums,index,bigIndex);
//            index = bigIndex;
//            left = (index<<1)+1;
//        }
    }


    //构建大跟堆
    public void heapInsert(int[] nums,int index){
        int parentIndex = (index-1)/2;
        while (parentIndex>=0&&nums[index]>nums[(index-1)/2]){
            SortUtils.swap(nums,index,(index-1)/2);
            index = (index-1)/2;
        }
//        while (nums[index]>nums[(index-1)/2]){
//            SortUtils.swap(nums,(index-1)/2,index);
//            index = (index-1)/2;
//        }
    }

}
